package com.example.algorithm.dynamicprogramming;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 *  示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 *  示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 */
public class Leetcode42_Trap {
    public static void main(String[] args) {
//        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] height = {4, 2, 0, 3, 2, 5};
//        int[] height = {3, 2, 1, 5, 4};

        System.out.println(new Solution().trap(height));

    }

    static class Solution {

        /**
         * 双指针方式
         * 从动态规划方法的只要 rightMax[i]>leftMax[i]，积水高度将由 leftMax 决定，类似地只要 leftMax[i]>rightMax[i],积水高度由rightMax决定。
         * 所以我们可以认为如果一端有更高的柱子（例如右端），积水的高度依赖于当前方向的高度（从左到右）。
         * 当我们发现另一侧（右侧）的柱子高度不是最高的，则开始从相反的方向遍历（从右到左）。
         * 我们必须在遍历时维护 leftMax 和 rightMax ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。
         *
         * @param height
         * @return
         */
        private int trap5(int[] height) {
            int left = 0, right = height.length - 1;
            int ans = 0;
            int leftMax = 0, rightMax = 0; // 分别记录从左到右的最大值和从右到左的最大值
            while (left < right) { //一旦发现leftMax或者rightMax在本次循环中不是最大的,就需要反向,每次循环要么left++,要么right--
                if (height[left] < height[right]) {
                    if (height[left] >= leftMax) {
                        leftMax = height[left];
                    } else {
                        ans += (leftMax - height[left]);
                    }
                    ++left;
                } else {
                    if (height[right] >= rightMax) {
                        rightMax = height[right];
                    } else {
                        ans += (rightMax - height[right]);
                    }
                    --right;
                }
            }
            return ans;
        }

        /**
         * 使用单调栈(单增栈新元素比栈顶大，单减栈新元素比栈顶小)
         *
         * 用栈来跟踪可能储水的最长的柱子。使用栈就可以在一次遍历内完成计算。
         *
         * 遍历数组时维护一个栈。如果当前的柱子小于或等于栈顶的柱子，将柱子的索引入栈，(不可能接收到雨水)
         * 如果现一个柱子长于栈顶，那么可以 确定栈顶的柱子 被 当前柱子 和  栈的前一个柱子界定  ，因此需要弹出栈顶元素并且计算柱子之间的雨水数量
         * 然后累加答案到res中
         *
         * @param height
         * @return
         */
        private int trap4(int[] height) {
            int sum = 0;
            Deque<Integer> stack = new LinkedList<>();
            int curIndex = 0;
            while (curIndex < height.length) {
                // 如果栈不空并且当前指向的高度大于栈顶高度就一直循环
                while (!stack.isEmpty() && height[curIndex] > height[stack.peek()]) {
                    int tmp = height[stack.pop()]; // 取出要出栈的元素
                    if (stack.isEmpty()) { // 栈空就退出
                        break;
                    }
                    int distance = curIndex - stack.peek() - 1; // 两堵墙之前的距离。
                    int min = Math.min(height[stack.peek()], height[curIndex]);
                    sum += distance * (min - tmp);
                }
                stack.push(curIndex); // 当前指向的高度小于栈顶高度就直接入栈
                curIndex++; // 指针后移
            }
            return sum;
        }

        /**
         * 动态规划
         * 暴力法每次求柱子的雨水数量都要向前和向后遍历找比当前柱子大的所有柱子里的第二大柱子
         * 我们可以提前存储这些值
         *
         * 1.原问题与子问题
         *   求第i根柱子能接收的雨水的数量res[i]
         *
         * 2.设计状态
         *   leftMaxs[i]表示到i之前的最大值;
         *   rightMaxs[j]表示j之后的最大值;
         *
         * 3.状态转移方程
         *   res[i] = min(leftMaxs[i], rightMaxs[i]) - height[i]
         *   目标值:sum(res)
         *
         * 4.初始状态:
         *   leftMaxs[0] = height[0];
         *   rightMaxs[length - 1] = height[length - 1]
         *
         * @param height
         * @return
         */
        private int trap3(int[] height) {
            int len = height.length;
            int res = 0;
            int[] leftMaxs = new int[len];
            int[] rightMaxs = new int[len];
            leftMaxs[0] = height[0];
            rightMaxs[len - 1] = height[len - 1];
            // 提前计算leftMaxs
            for (int i = 1; i < len; i++) {
                leftMaxs[i] = Math.max(height[i], leftMaxs[i - 1]);
            }
            // 提前计算rightMaxs
            for (int i = len - 2; i >= 0; i--) {
                rightMaxs[i] = Math.max(height[i], rightMaxs[i + 1]);
            }

            for (int i = 1; i < len - 1; i++) {
                res += Math.min(leftMaxs[i], rightMaxs[i]) - height[i];
            }
            return res;
        }

        /**
         * 暴力法二:一根一根柱子求能接雨水的数量(按列求)
         * 思路:
         * 需要关注当前列，以及左边最高的墙，右边最高的墙就够了。
         * 装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了
         *
         * 遍历柱子,在每根柱子分别向前和向后遍历找到比当前柱子大的最大值,
         * 然后用两者的较小值(得到比当前柱子大的第二大的值)减去当前柱子高度就是该跟柱子能接的雨水数量
         * @param height
         * @return
         */
        private int trap2(int[] height) {
            int res = 0;
            for (int i = 0; i < height.length; i++) {
                // 向前找到大于当前值的最大值
                int leftMax = height[i];
                for (int j = i - 1; j >= 0; j--) {
                    leftMax = Math.max(leftMax, height[j]);
                }
                // 向后找到大于当前值的最大值
                int rightMax = height[i];
                for (int k = i + 1; k < height.length; k++) {
                    rightMax = Math.max(rightMax, height[k]);
                }
                // 得到当前柱子能接雨水的高度并累加
                res += Math.min(leftMax, rightMax) - height[i];
            }
            return res;
        }

        /**
         * 暴力法(超时)
         * 一层一层求解
         * @param height
         * @return
         */
        private int trap1(int[] height) {
            int max = 0;
            int res = 0;
            // 求出数组最大值
            for (int i = 0; i < height.length; i++) {
                max = Math.max(max, height[i]);
            }

            // 一层一层的算出能接雨水的数量
            for (int i = 1; i <= max; i++) {
                int layerSum = 0;
                boolean flag = false;// 是否该计算该层雨水数量
                for (int j = 0; j < height.length; j++) {
                    if (flag && height[j] < i) {
                        layerSum++;
                    }

                    if (height[j] >= i) {
                        flag = true;
                        res += layerSum;
                        layerSum = 0;
                    }

                }
            }
            return res;
        }

        public int trap(int[] height) {
            return trap4(height);
        }
    }
}
